// 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

// 示例:

// 给定 nums = [2, 7, 11, 15], target = 9

// 因为 nums[0] + nums[1] = 2 + 7 = 9
// 所以返回 [0, 1]


/**
 * https://leetcode.cn/problems/two-sum/
 * 解题思路：
 * 1.把余数的位置缓存到对象里，后面计算时检查是否有缓存
 * 2.数组可以是无序或者已排序的
 * O(n)
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 var twoSum = function(nums, target) {
    let map=new Map();
    for(let i=0;i<nums.length;i++){
       let res=target-nums[i];
        if(map.has(res)){
            return [map.get(res),i]
        }
        map.set(nums[i],i)
    }
    return []
};

/**
 * 暴力破解：1个个对比，O(n^2)
 * */
var twoSum2 = function(nums, target) {
   
    for(let i=0;i<nums.length-1;i++){
       for (let j = i+1; j < nums.length; j++) {
        let sum=nums[i]+nums[j]
        if(sum==target){
            return [i+1,j+1]
        }
        console.log(i,j,sum)
       }
    }
    return []
};

/*
双指针解法
解题思路:
由于Nums是有序的从小到大，那么
我们通过两个指针指向开始和结尾，当结果只有大于，等于，或者小于
大于则移动右指针，因为无论nums[1...right]+nums[right]都是大于，所以要right-1
小于则移动左指针,因为无论nums[left]+nums[left...n]都是小于，所以要left-1
等于直接返回结果
为什么能做到O（n）,因为每次移动指针时可以减少1轮的检查，如果数组是无序的话，这个方案就不行
因为left不可能大于right,所以不可能遗漏结果
*/
var twoSum3 = function(nums, target) {
    let left=0;
    let right=nums.length-1;
    while(left<right){
        let sum=nums[left]+nums[right];
        if(sum===target)return [left+1,right+1]
        if(sum>target){right--}else{
            left++;
        };
        // if(sum<target)
    }

    return []
};


console.log(twoSum3([2,3,4,5,6],6))
console.log(twoSum3([2,7,11,15],9))
